package offer2

/*
原题链接:
https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

剑指offer 19.正则表达式匹配
题目描述：请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。
模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"aba"均不匹配
*/
func isMatch(s string, p string) bool {
	//1.获取行,列数
	row, col := len(s), len(p)

	//2.声明二维数组
	table := make([][]bool, row+1)
	for i := 0; i < len(table); i++ {
		table[i] = make([]bool, col+1)
	}

	//3.设置dp[0][0]的初始值true
	table[0][0] = true

	//先将p,s转化为字符切片
	pRunes := []rune(p) //表达式的字符切片
	sRunes := []rune(s)

	//4.初始化第0行布尔值
	for col := 1; col < len(table[0]); col++ {
		//获取p的0位置
		ch := pRunes[0]
		if col > 1 {
			if ch == '*' {
				table[0][col] = table[0][col-2]
			} else {
				table[0][col] = false
			}
		} else {
			if ch == '*' {
				table[0][col] = true
			}
		}
	}

	//5.遍历填充dp数组
	for row := 1; row < len(table); row++ {
		ch1 := sRunes[0]                             //s的0索引字符
		for col := 1; col < len(table[row]); col++ { //从1列开始,col列数要小于table的row行数
			ch2 := pRunes[col-1]

			if ch1 == ch2 || ch2 == '.' {
				table[row][col] = table[row-1][col-1]
			} else if ch2 == '*' {
				if col > 1 {
					if table[row][col-2] {
						table[row][col] = true //* 前面的字符出现的次数
					} else {
						prev := pRunes[col-2] //应该是-1, 但是二维数组的列数+1了, 所以-2才能对应上
						if prev == ch1 || prev == '.' {
							table[row][col] = table[row-1][col] // *前的字符出现多次
						}
					}
				}
			}
		}
	}

	lastRow := table[len(table)-1]
	return lastRow[len(lastRow)-1]
}
